package bTree.LeetCode;

import java.util.List;

public class 三角形最小路径和 {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle==null||triangle.size()==0){
            return 0;
        }
        int row=triangle.size();
        if(triangle.size()==1){
            return triangle.get(0).get(0);
        }
        if(triangle.size()==2){
            return triangle.get(0).get(0)+Math.min(triangle.get(1).get(0),triangle.get(1).get(1));
        }
        int [][]dp=new int[row][triangle.get(row-1).size()];
        dp[0][0]=triangle.get(0).get(0);
        dp[1][0]=dp[0][0]+triangle.get(1).get(0);
        dp[1][1]=dp[0][0]+triangle.get(1).get(1);
        for(int i=2;i<row;i++){
            int line=triangle.get(i).size();
            for(int j=0;j<line;j++){
                if(j==0){
                    dp[i][j]=dp[i-1][j]+triangle.get(i).get(j);
                } else if (j==line-1) {
                    dp[i][j]=dp[i-1][j-1]+triangle.get(i).get(j);
                }else{
                    dp[i][j]=Math.min(dp[i-1][j],dp[i-1][j-1])+triangle.get(i).get(j);
                }
            }
        }
        int min=Integer.MAX_VALUE;
        for (int i : dp[row - 1]) {
            min=Math.min(min,i);
        }
        return min;
    }
}